package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 2096. 从二叉树一个节点到另一个节点每一步的方向
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/6 17:50
 */
public class GetDirections {

    public String getDirections(TreeNode root, int startValue, int destValue) {
        List<String> a = new ArrayList<>();
        List<String> b = new ArrayList<>();
        find(a, root, startValue);
        find(b, root, destValue);
        int i = a.size() - 1;
        int j = b.size() - 1;
        while (i >= 0 && j >= 0) {
            if (!a.get(i).equals(b.get(j))) {
                break;
            }
            i--;
            j--;
        }
        StringBuilder sb = new StringBuilder(j + i + 2);
        for (int n = 0; n <= i; n++) {
            sb.append("U");
        }
        for (int n = j; n >= 0; n--) {
            sb.append(b.get(n));
        }
        return sb.toString();
    }

    private boolean find(List<String> list, TreeNode node, int value) {
        if (node == null) {
            return false;
        }
        if (node.val == value) {
            return true;
        }
        if (find(list, node.left, value)) {
            list.add("L");
            return true;
        }
        if (find(list, node.right, value)) {
            list.add("R");
            return true;
        }
        return false;
    }

}
